An ad hoc network is a group of wireless nodes that cooperatively form a network independent of fixed infrastructure or centralized administration. In the absence of a fixed infrastructure, nodes in ad hoc networks cooperate to provide routing services, relying on each other to forward packets to their destination. Since there is no centralized control to enforce cooperation, and devices in an ad hoc network may belong to different authorities such as different persons, wireless nodes may attempt to be selfish and unwilling to spend their own bandwidth and battery power in forwarding packets for other users. This is a fundamental problem for ad hoc networks and has been attracting researchers' interests since ad hoc network was first introduced.
Since the problem of selfish nodes is very fundamental to ad hoc networks, many research works have been conducted on stimulating cooperation among non-cooperative nodes for data forwarding. Those works basically can be divided into two categories: reputation based and credit-exchange based.
In reputation based solutions, network nodes monitor other nodes' behaviors and make a reputation for one another. If a node is selfish, for example, dropping other nodes' packets, it will get a bad reputation and be isolated by other nodes. These solutions usually require network nodes to propagate second-hand reputation information, so the secured reputation propagation incurs a new security problem in the existing systems. Another serious issue is that these systems generally cannot prevent colluding to cheat.
In credit-exchange based solutions, nodes are paid with credits each time when they forward a packet for others. If a selfish node doesn't forward packets for others, it has no credit to pay others for sending its own data. Such solution requires systems such as the virtual bank to manage the exchange of credits, which can be very complex. Some existing works even use tamper-proof hardware module to secure credit information. Moreover, after a node gains enough credits for transmitting its own data, it can start to drop others' packets.
Although the above two types of solutions appear quite different from each other, their basic ideas are similar: building a context for recording and tracking nodes' behaviors, evaluating whether a node is selfish in terms of the cumulated reputation or credit, and punishing the selfish nodes. These solutions are context-based solutions, which depend on continuously tracking the behaviors of all the network nodes for forwarding the packets among multiple traffic flows. In addition, context-based solutions rely on accurate identification of selfish behaviors, securely maintaining the context, and appropriately punishing the selfish nodes. Although many context-based systems have been proposed, none of them is able to completely meet all these requirements. Moreover, isolating selfish nodes after identifying them is an inefficient way for solving the selfish node problem, since a longer transmission path will likely have to be used in order to bypass the selfish nodes.
Unlike context-based protocols that rely on information collected from transmissions of other packets, the network nodes in context-free protocols are able to transmit a packet over a path without relying on the transmissions of other packets. Such a protocol has significant advantages over context-based ones. Firstly, context-free protocols only rely on a single packet to make transmission decision over multiple hops. They are not required to maintain and secure context information, and therefore avoid all the issues caused by the context maintenance. Secondly, context-free protocols are not required to track all the packets and check context information, and therefore operate immediately when a packet is transmitted. Thirdly, context-free protocols are not required to obtain the information of other traffic flows, and therefore function well with any traffic pattern.
Existing context-free protocols, however, are very vulnerable to colluding and flow analysis attacks. In addition, the designs of existing context-free protocols result in high latency and are likely to cause problems to latency-sensitive network transmissions such as TCP. Therefore, it is desired to design a context-free protocol for ad hoc network to stimulate and encourage data forwarding among a plurality of network nodes, wherein the protocol is robust and not subject to colluding and flow analysis attacks.